import  java.util.*;
public class Test14_1 {
    public static int maxProductAfterCutting_1(int length){
        if (length == 3) return 3;
        if (length == 2) return 1;
        if (length < 2) return 0;

        int[] dp = new int[length+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;

        int max = 0;
        for (int i = 4;i<=length;i++){
            max = 0;
            for(int j = 1; j<= i/2;j++){
                int temp = dp[j] * dp[i-j];
                if (temp > max) max = temp;
                dp[i] = max;
            }
        }
        max = dp[length];
        return max;

    }

    public static int maxProductAfterCutting_2(int length){
        if (length == 3) return 3;
        if (length == 2) return 2;
        if (length < 2) return 0;

        //尽可能的剪长度为3的长度
        int timeof3 = length /3;
        if (length - timeof3*3 == 1)   timeof3 -= 1;
        int timeof2 = (length-timeof3*3)/2;
        return (int)Math.pow(3,timeof3) * (int)Math.pow(2,timeof2);
    }

    public static void main(String[] args) {
        System.out.println(maxProductAfterCutting_1(5));
        System.out.println(maxProductAfterCutting_2(5));
    }
}
